﻿namespace _42接雨水
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[] { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
            Solution.Trap(nums);
        }
    }
    public class Solution
    {
        public static  int Trap(int[] height)
        {

            int n = height.Length;
            if (n == 0)
                return 0;

            int[] leftMax = new int[n];
            int[] rightMax = new int[n];

            leftMax[0] = height[0];
            for (int i = 1; i < n; i++)
            {
                leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
            }

            rightMax[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i--)
            {
                rightMax[i] = Math.Max(rightMax[i + 1], height[i]);
            }

            int totalWater = 0;
            for (int i = 0; i < n; i++)
            {
                int waterHeight = Math.Min(leftMax[i], rightMax[i]);
                int waterLevel = waterHeight - height[i];
                totalWater += waterLevel;
            }

            return totalWater;
        }


        public int trap(int[] height)
        {
            int sum = 0;
            //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
            for (int i = 1; i < height.Length - 1; i++)
            {
                int max_left = 0;
                //找出左边最高
                for (int j = i - 1; j >= 0; j--)
                {
                    if (height[j] > max_left)
                    {
                        max_left = height[j];
                    }
                }
                int max_right = 0;
                //找出右边最高
                for (int j = i + 1; j < height.Length; j++)
                {
                    if (height[j] > max_right)
                    {
                        max_right = height[j];

                    }
                }
                //找出两端较小的
                int min = Math.Min(max_left, max_right);
                //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
                if (min > height[i])
                {
                    sum = sum + (min - height[i]);
                }
            }
            return sum;
        }

    
    }
}
